package dynamic;

/**
 * p189
 * 换钱最少的货币数
 *
 * @author 罗俊华
 * @date 2021/7/21 - 4:51 下午
 */
public class ExchangeMoney {

    /**
     * @param availableMoney 可用于找零的钱的面值，要求从大到小排序
     * @param money          要找零的金额
     * @return index对应 availableMoney 的索引，代表对应面值的钱因该要 result[index] 张
     */
    public static int[] exchange(int[] availableMoney, int money) {

        int index = 0;

        int[] result = new int[availableMoney.length];

        while (true) {

            if (money >= availableMoney[index]) {

                result[index] = money / availableMoney[index];
                money = money % availableMoney[index];

                if (money == 0) {
                    break;
                }
            }
            index++;
            if (index >= availableMoney.length) {
                throw new RuntimeException("无法找零");
            }
        }
        return result;

    }


}
